//给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含 最少 数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减
// 顺序的。根据前面描述，构造 powers 数组的方法是唯一的。 
//
// 同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] ，其中 queries[i]
// 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。 
//
// 请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将
//每个 answers[i] 都对 10⁹ + 7 取余 。 
//
// 
//
// 示例 1： 
//
// 输入：n = 15, queries = [[0,1],[2,2],[0,3]]
//输出：[2,4,64]
//解释：
//对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
//第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。
//第 2 个查询的答案：powers[2] = 4 。
//第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 
//。
//每个答案对 10⁹ + 7 得到的结果都相同，所以返回 [2,4,64] 。
// 
//
// 示例 2： 
//
// 输入：n = 2, queries = [[0,0]]
//输出：[2]
//解释：
//对于 n = 2, powers = [2] 。
//唯一一个查询的答案是 powers[0] = 2 。答案对 10⁹ + 7 取余后结果相同，所以返回 [2] 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 10⁹ 
// 1 <= queries.length <= 10⁵ 
// 0 <= starti <= endi < powers.length 
// 
//
// Related Topics 位运算 数组 前缀和 👍 36 👎 0


package LeetCode.editor.cn;


import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-08-11 10:01:14
 * @description 2438.二的幂数组中查询范围内的乘积
 
 */
 
public class RangeProductQueriesOfPowers {
    public static void main(String[] args) {
    //测试代码
    RangeProductQueriesOfPowers fun = new RangeProductQueriesOfPowers();
    Solution solution= fun.new Solution();
    solution.productQueries(15,new int[][]{{0,1},{2,2},{0,3}});
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] productQueries1(int n, int[][] queries) {
        // 首先找到 n 的二进制表示中所有的 1 的位置
        // 然后将这些位置对应的 2 的幂存储在一个数组中
        // 接着对于每个查询，计算对应范围内的乘积
        // 由于乘积可能非常大，我们需要对结果取模 10^9 + 7
        int mod = 1000000007;
        int [] powers = new int[32];
        while (n > 0) {
            // Integer.highestOneBit 和 Integer.bitCount
            // 可以用来找到 n 的最高位的 1 和 1 的个数
            int power = Integer.highestOneBit(n);
            powers[Integer.bitCount(n) - 1] = power;
            n -= power;
        }
        int[] results = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            long product = 1;
            for (int j = left; j <= right; j++) {
                product = (product * powers[j]) % mod;
            }
            results[i] = (int) product;
        }
        return results;
    }
    //优化，每一位和前缀和同时预计算
    public int[] productQueries(int n, int[][] queries) {
        int mod = 1000000007;
        List<Integer> powers = new ArrayList<>();

        // 分解n为2的幂次和
        for (int i = 0; i < 32; i++) {
            if ((n & (1 << i)) != 0) {
                powers.add(1 << i);
            }
        }

        // 计算前缀积数组
        int[] prefix = new int[powers.size() + 1];
        prefix[0] = 1;
        for (int i = 0; i < powers.size(); i++) {
            prefix[i + 1] = (int)((long)prefix[i] * powers.get(i) % mod);
        }

        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];

            // 计算区间乘积
            long product = (long)prefix[right + 1] * modInverse(prefix[left], mod) % mod;
            result[i] = (int)product;

            // 处理可能的负数结果
            if (result[i] < 0) {
                result[i] += mod;
            }
        }

        return result;
    }

    // 计算模逆元（使用费马小定理）
    // 当 mod 是质数时，a 的模逆元可以通过 a^(mod-2) % mod 计算
    private int modInverse(int a, int mod) {
        return power(a, mod - 2, mod);
    }

    // 快速幂计算
    private int power(int x, int y, int mod) {
        int res = 1;
        x = x % mod;
        while (y > 0) {
            if ((y & 1) == 1) {
                res = (int)((long)res * x % mod);
            }
            y >>= 1;
            x = (int)((long)x * x % mod);
        }
        return res;
    }


    /*
    * 逆元
    * 1. 现实中的"倒数"（先理解这个）
        比如数字 5，它的倒数是 1/5（即0.2），因为：
        5 × (1/5) = 1
        这里 1/5 就是 5 的"逆元"（因为乘起来等于1）。
      2. 模运算下的"倒数"（模逆元）
        现在进入模运算世界（比如模 7），我们想找一个数 x，使得：
        5 × x ≡ 1 (mod 7)
        （意思是：5×x除以7余1）
        试错法找x：
            5×1 = 5 → 5%7=5 ✖（不等于1）
            5×2 = 10 → 10%7=3 ✖
            5×3 = 15 → 15%7=1 ✔
            所以 x=3 就是5在模7下的逆元！
        验证：
            5 × 3 = 15
            15 ÷ 7 = 2余1 → 所以15 ≡ 1 (mod 7) ✅
      3. 为什么需要模逆元？
        问题：模运算中不能直接做除法（比如算 (a/b) mod p），但可以改成乘法：
            (a × b⁻¹) mod p
            （其中 b⁻¹ 是b的模逆元）
        例子：计算 (8/4) mod 7
            → 先找4的模逆元（即x，使得4x≡1 mod 7）
            → x=2（因为4×2=8≡1 mod 7）
            → 所以 (8 × 2) mod 7 = 16 mod 7 = 2 ✅
            （直接算8/4=2，结果一致）
      4. 如何快速计算模逆元？
        当模数 p 是质数时（比如题目中的1e9+7），用费马小定理：
        如果 p是质数，且a和p互质，则：
        a⁻¹ ≡ a^(p-2) mod p
        例子：求5在模7下的逆元
        → 计算5^(7-2) = 5^5 = 3125
        → 3125 mod 7 = 3 ✅（和我们之前试错的结果一致）
      5. 代码中的实际应用
        // 计算a的模逆元（mod为质数）
        int inv(int a, int mod) {
            return power(a, mod-2, mod); // 快速幂计算a^(mod-2)
        }

        // 快速幂计算（x^y mod p）
        int power(int x, int y, int p) {
            int res = 1;
            x = x % p;
            while (y > 0) {
                if (y % 2 == 1) {
                    res = (res * x) % p;
                }
                y = y >> 1;
                x = (x * x) % p;
            }
            return res;
        }
      6. 一句话总结
      模逆元就是模世界里的倒数，用来把除法变成乘法：
        (a / b) mod p = (a × b⁻¹) mod p
        其中 b⁻¹ 是b的模逆元，满足 b × b⁻¹ ≡ 1 (mod p)。
    *
    *
    * */
}
//leetcode submit region end(Prohibit modification and deletion)

}
